package java学习.leetcode.editor.cn;
/**
 * @author 刘世锦
 */
// 给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
//
// 每步 可以删除任意一个字符串中的一个字符。 
//
// 
//
// 示例 1： 
//
// 
//输入: word1 = "sea", word2 = "eat"
//输出: 2
//解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

/**         j
 *        "" e a t
 *         0 1 2 3
 *   "" 0  0 1 2 3
 * i  s 1  1 2 3 4
 *    e 2  2 1 2 3
 *    a 3  3 2 1 2
 *
 *
 */
// 示例 2:
//  e t c o
//  l e e t c o d
//  e
//输入：word1 = "leetcode", word2 = "etco"
//输出：4

import java.util.Arrays;

/**      j
 *       0 1 2 3 4
 * i    "" e t c o
 * 0 ""  0 1 2 3 4
 * 1 l   1 2 3 4 5
 * 2 e   2 1 2 3 4
 * 3 e   3 2 3 4 5
 * 4 t   4 3 2 3 4
 * 5 c   5 4 3 2 3
 * 6 o   6 5 4 3 2
 * 7 d   7 6 5 4 3
 * 8 e   8 7 6 5 4
 *
 *
 */
// 
//  dp[i][j] 前0~i-1 的word1子序列中 凑成 word2 0~j-1子序列的步数
// 
//
// 提示： 
// 
//
// 
// 1 <= word1.length, word2.length <= 500 
// word1 和 word2 只包含小写英文字母 
// 
// Related Topics 字符串 动态规划 
// 👍 491 👎 0

public class 两个字符串的删除操作{
	public static void main(String[] args) {
		Solution solution = new 两个字符串的删除操作().new Solution();
		String	word1 = "leetcode", word2 = "etco";
//		String 	word1 = "sea", word2 = "eat";
//		String	word2 = "park", word1 = "spake";
//		                                 park  pak
//		String word1 = "a",word2  = "b";
		System.out.println(solution.minDistance(word1,word2));
		
	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	public int minDistance1(String word1, String word2) {
//   	需要 从0开始判断"" 空串的情况
//    	找到最长公共子序列，一减就行
		int w1  = word1.length(),w2 = word2.length();
		int [][] dp = new int[w1+1][w2+1];
		int max = 0;
		for (int i = 1; i < w1+1; i++) {
			for (int j = 1; j < w2+1; j++) {
				if (word1.charAt(i-1)==word2.charAt(j-1)){
					dp[i][j] = dp[i-1][j-1]+1;
				}else{
					dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
				}
				max = Math.max(max,dp[i][j]);
			}
		}
		for (int i = 0; i < word1.length()+1; i++) {
			for (int j = 0; j < word2.length()+1; j++) {
				System.out.print(dp[i][j]+" ");
			}
			System.out.println();
		}
		int result = w1+w2-2*max;
		// System.out.println(result);
		return result;
	}
	public int minDistance(String word1, String word2) {

		//		打表时，可能 dp[i][j]来自 其他三个方向+1
		int w1  = word1.length(),w2 = word2.length();
		int [][] dp = new int[w1+1][w2+1];
		for (int i = 0; i < w1+1; i++) {
//			当w2为空串时，其最小删除次数为 i（w1的长度）
			dp[i][0] = i;

		}
		for (int i = 0; i < w2+1; i++) {
//			当w1为空串时，其最小删除次数为 i（w2的长度）
			dp[0][i] = i;
		}
		for (int i = 1; i < w1+1; i++) {
			for (int j = 1; j < w2+1; j++) {
				if (word1.charAt(i-1)==word2.charAt(j-1)){
//					相等，则不需要删除字符
					dp[i][j] = dp[i-1][j-1] ;
				}else{
//					取 dp[i][j-1]+1 , dp[i-1][j]+1 , dp[i-1][j-1]+2 的最小值
					dp[i][j] = Math.min(dp[i-1][j]+1,dp[i][j-1]+1);
//					dp[i][j] = Math.min(dp[i-1][j-1]+2,dp[i][j]);
				}
//				max = Math.max(max,dp[i][j]);
			}
		}
		for (int i = 0; i < word1.length()+1; i++) {
			for (int j = 0; j < word2.length()+1; j++) {
				System.out.print(dp[i][j]+" ");
			}
			System.out.println();
		}
		return dp[w1][w2];

	}

	}
//leetcode submit region end(Prohibit modification and deletion)

}
